package leetcode_801_900;

import javafx.scene.effect.SepiaTone;

import java.util.*;

public class LeeCode_805 {
    public static void main(String[] args) {
        System.out.println(splitArraySameAverage(new int[]{3, 1}));
        System.out.println(splitArraySameAverage(new int[]{1,2,3,4,5,6,7,8}));
        System.out.println(splitArraySameAverage(new int[]{18, 0, 16, 2}));
    }
    private static boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return false;
        int m = n / 2;
        Set<Integer> set = new HashSet<>();
        int sum = Arrays.stream(nums).sum();
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] * n - sum;
        }
        for(int i = (1 << m) - 1, bit = i; i > 0; i = (i - 1) & bit){
            int tol = 0;
            for (int j = 0; j < m; j++) {
                if ((i & (1 << j)) != 0){
                    tol += nums[j];
                }
            }
            if (tol == 0)
                return true;
            set.add(tol);
        }
        int rSum = 0;
        for (int i = m; i < n; i++) {
            rSum += nums[i];
        }
        for(int i = (1 << (n - m)) - 1, bit = i; i > 0; i = (i - 1) & bit){
            int tol = 0;
            for (int j = m; j < n; j++) {
                if ((i & (1 << (j - m))) != 0){
                    tol += nums[j];
                }
            }
            if (tol == 0 || (rSum != tol && set.contains(-tol)))
                return true;
        }
        return false;
    }
}